For this homework, there is no starter file. You have to create your own .py file and submit it to Autolab. You can take a previous starter file and modify it appropriately.
Please add your name, Andrew id, and section at the top of the file.
Write test functions for each function you write.
APPLY TOP-DOWN DESIGN, USE LOTS OF HELPER FUNCTIONS.
IMPORTANT: Make sure you put all test functions and manually graded functions below #ignore_rest.
You will be graded on style. You can lose up to 10 poins for style (out of 100 points). Please see here for the style rubric.
You may not use recursion, sets, dictionaries or any other constructs that we have not yet covered in class.
You will have 5 submissions on Autolab for this homework.
Questions
1. Better Big Oh [15 pts][manually graded]
In a triple-quoted string at the top of your file (just below your name), include solutions to this exercise. For each of the following functions:
- State in just a few words what it does in general.
- State and prove (in a few words) its worst-case big-oh runtime.
You should assume that lists all contain at least 5 values, and only integer values. Also, if a function takes two lists, you should assume they are the same length N.
import copy
def slow1(a):
(b, c) = (copy.copy(a), 0)
while (b != [ ]):
b.pop()
c += 1
return c
def slow2(a):
n = len(a)
count = 0
for i in range(n):
for j in range(n):
if (a[i] == a[j]):
count += 1
return (count == n)
def slow3(a, b):
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = 0
for c in b:
if c not in a:
result += 1
return result
def slow4(a, b):
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = abs(a[0] - b[0])
for c in a:
for d in b:
delta = abs(c - d)
if (delta > result):
result = delta
return result
def slow5(a, b):
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = abs(a[0] - b[0])
for c in a:
for d in b:
delta = abs(c - d)
if (delta < result):
result = delta
return result
2. nearestKaprekar(n) [30 pts] [autograded]
See question 9 from
here.
Hint: one way to solve this is to start at n and grow in each direction until you find a Kaprekar number.
3. hasBalancedParentheses(s)[15 pts] [autograded]
See question 6 from
here.
3. unboundedNumberGuessing(n) [30 pts] [autograded]
As we covered in class, guessing a number between 1 and N is a basic application of binary search. But what if you don't know the upper bound? Or even the lower bound? What if I asked you to guess the number I am thinking of, and I tell you nothing of its value. It might be 42, but it might be -42 quadrillion. Hmmm. To solve this, first guess 0. If it is right, you're done! Amazing luck! Otherwise, if it is too low, we know N is positive. In that case, we have to determine an upper bound for N. How? Try 1. If that is too low, double it to 2. And keep going until you find your upper bound. This is kind of like inverse binary search. Cool! Also note that you know your lower bound is the next-to-last value you tried. So if N==5, you would guess 1, then 2, then 4, then 8, and at that point you would know that N is between 4 and 8. Actually, since you'd know that 4 and 8 could not be N, you would know N is between 5 and 7 inclusively. Now, what if N is negative, and our first guess of 0 was too high? Then you would do the analogous operations to find the lower bound. In any case, once bounded above and below, this reduces to everyday binary search.
With this in mind, write the function unboundedNumberGuessing(n) that takes an integer value n and returns a comma-separated string of all the values in order required to find the value n.
So, for example:
unboundedNumberGuessing(42) returns "0,1,2,4,8,16,32,64,48,40,44,42"
and
unboundedNumberGuessing(-13) returns "0,-1,-2,-4,-8,-16,-12,-14,-13"
4. selectionSort and bubbleSort modifications[10 pts] [manually graded]
1. selectionSort
In class we developed the following code for selectionSort:
def selectionSort(a):
n = len(a)
for startIndex in range(n):
minIndex = startIndex
for i in range(startIndex, n):
if (a[i] < a[minIndex]):
minIndex = i
(a[minIndex], a[startIndex]) = (a[startIndex], a[minIndex])
This implementation first finds the smallest element in the lists and swaps it with the element in the first position, then find the second smallest element and swaps it with the element in the second position, and continue in this way until the entire lists is sorted.
Modify this code such that instead, in the first iteration we find the largest element and swap it with the element in the last position, then find the second largest element and swap it with the element in the second to last position and so on until the array is sorted. Turn in this newly modified code as part of you solution.
2. bubbleSort
In class we developed the following code for bubbleSort:
def bubbleSort(a):
end = len(a) - 1
swapped = True
while (swapped):
swapped = False
for i in range(end):
if (a[i] > a[i + 1]):
(a[i], a[i+1]) = (a[i+1], a[i])
swapped = True
end -= 1
This implementation "bubbles up" the largest element to the end of the array in each iteration until all the elements are sorted. Modify this code such that instead, the smallest elements are "bubbled down" to the front of the array in each iteration until all the elements are sorted.
